public class BinarySearchTree {
    static class TreeNode {
        public int val;
        public TreeNode left;
        public TreeNode right;

        public TreeNode(int val) {
            this.val = val;
        }
    }
    //当前搜索树的根节点
    public TreeNode root = null;

    public TreeNode search(int val) {
        TreeNode cur = root;
        while (cur != null) {
            if(cur.val < val) {
                cur = cur.right;
            }else if(cur.val > val) {
                cur = cur.left;
            }else {
                return cur;
            }
        }
        return null;
    }

    //搜索树的节点增加
    public void insert(int val) {
        if(root == null) {
            root = new TreeNode(val);
            return;
        }

        TreeNode cur = root;
        TreeNode par = null;
        while(cur != null) {
            if(cur.val > val) {
                par = cur;
                cur = cur.left;
            }else if(cur.val < val) {
                par = cur;
                cur = cur.right;
            }else {
                return;
            }
        }

        if(par.val > val) {
            par.left = new TreeNode(val);
        }else {
            par.right = new TreeNode(val);
        }

    }

    //删除节点
    public void remove(int val) {

        TreeNode cur = root;
        TreeNode par = null;

        while(cur != null) {
            if(cur.val > val) {
                par = cur;
                cur = cur.left;
            }else if(cur.val < val) {
                par = cur;
                cur = cur.right;
            }else {
                Delate(par,cur);
                return;
            }
        }

    }

    public void Delate(TreeNode par,TreeNode cur) {
        if(cur.left == null) {
            if(cur == root) {
                root = cur.right;
            }else if(cur == par.left){
                par.left = cur.right;
            }else {
                par.right = cur.right;
            }
        }else if(cur.right == null) {
            if(cur == root) {
                root = cur.left;
            }else if(cur == par.left){
                par.left = cur.left;
            }else {
                par.right = cur.left;
            }
        }else {
            TreeNode stay = cur;
            TreeNode move = cur.left;
            while(move.right != null) {
                stay = move;
                move = move.right;
            }
            cur.val = move.val;;
            if(stay.left == move) {
                cur.left = move.left;
            }else {
                stay.right = move.left;
            }
        }
    }

}
